Bienvenue au Cours 2. Après avoir défini les objectifs généraux de ce cours, nous explorons maintenant les structures fondamentales structures de données qui constituent les briques élémentaires de la conception d'algorithmes : les tableaux et les listes chaînées.
Les tableaux et les listes chaînées sont les méthodes les plus fondamentales et essentielles pour organiser les données en mémoire, incarnant le conflit central entre contiguës et dispersées la gestion de stockage.
Définition :Une structure de données est un format spécialisé pour organiser et stocker des données afin de faciliter leur accès et leur modification efficaces.
- Les tableaux stockent les éléments dans des emplacements contiguësmémoire, permettant un calcul direct des adresses des éléments.
- Les listes chaînées stockent les éléments dans des emplacements disperséesmémoire, reliés uniquement par des pointeurs explicites.
- L'accès au tableau est indexation directe ($O(1)$), tandis que l'accès à une liste chaînée nécessite parcours ($O(n)$).
- L'insertion/suppression dans un tableau nécessite le décalage des éléments, entraînant une complexité de $O(n)$ complexité.
- L'insertion/suppression dans une liste chaînée ne nécessite que la reconnexion des pointeurs, permettant une complexité de $O(1)$ si la position $i$ est connue.
- Les listes chaînées engendrent un surcoût d'espacecar chaque nœud doit stocker les données ainsi qu'un pointeur `next`.
Comparaison des complexités
| Fonctionnalité | Tableau | Liste chaînée simple |
|---|---|---|
| Allocation mémoire | Contiguë (taille fixe du bloc $n$) | Dispersée (pointeurs dynamiques) |
| Temps d'accès | $O(1)$ | $O(n)$ |
| Insertion/Suppression | $O(n)$ | $O(1)$ (si la position $i$ est connue) |
| d'espace | Minimal (données uniquement) | Élevé (données + suivantpointeur) |